package cn.xiaolang.function.data_structure;

/**
 * 求平方根:
 *
 * <p>
 * 给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
 * 正数的平方根有两个，只输出其中的正数平方根。
 * <p>
 * 如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
 * <p>
 * 示例 1:
 * 输入: x = 4
 * 输出: 2
 *
 * <p>
 * 示例 2:
 * 输入: x = 8
 * 输出: 2
 * 解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2
 * <p>
 * 提示: 0 <= x <= 231 - 1
 */
public class No11sqrt {

    public static void main(String[] args) {
        System.out.println(mySqrt(6));
    }

    /**
     * left-------mid------right
     * 0----------------------8
     * 0----------4-----------8
     * 0----------------------3   right: mid-1
     * 0----------1-----------3   left: mid+1
     * 2----------------------2   mid: left, left: mid+1
     **/
    public static int mySqrt(int x) {
        int left = 0, right = x, rt = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long) mid * mid <= x) {
                rt = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return rt;
    }
}
